package I.堆;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

public class _703_数据流中的第K大元素 {

    /**
     * 构建大顶堆 构造器中构造好队列 add后 先offor 再根据k值循环遍历peek的next
     * ==没有next方法
     * ---超时了
     */

//    private int k;
//    private PriorityQueue<Integer> queue;


//    public _703_数据流中的第K大元素(int k, int[] nums) {
//        this.k = k;
//        queue = new PriorityQueue<>((n1,n2)->n2-n1);
//        for (int num:nums){
//            queue.offer(num);
//        }
//
//    }
//
//    public int add(int val) {
//        queue.offer(val);
//
//        int count = k;//不妨碍下一次遍历
//        int rs=0;
//        ArrayList<Integer> list = new ArrayList<>();
//        while (count >0){
//            list.add(queue.poll());//先取出来
//        }
//        for (int num:list){
//            queue.offer(num);//再放回去
//        }
//
//        return list.get(list.size()-1);
//    }

    /**
     * 题解：：直接设置一个大小为k的小顶堆 从原始数组入栈就开始
     * 那么堆顶就是最小的判断来的那个数字 如果大于堆顶就 替换堆顶 如果小于 那么前k个最大的还是当前堆
     */

    private int k;
    private PriorityQueue<Integer> queue;
    public _703_数据流中的第K大元素(int k, int[] nums) {
        this.k = k;
        queue = new PriorityQueue<>(k);

        for (int num:nums){
            add(num);
        }

    }
    public int add(int val) {

        if (queue.size()<k){
            queue.offer(val);
        }

        if (queue.peek() < val){
            queue.poll();
            queue.offer(val);
        }

        return queue.peek();


    }


}
